# 1823 中等：找出游戏的获胜者
from collections import deque


def findTheWinner(n, k):
    q = deque(range(1, n + 1))
    while len(q) > 1:
        for _ in range(k - 1):
            q.append(q.popleft())
        q.popleft()
    return q[0]


print(findTheWinner(6, 5))


# class Solution:
#     def findTheWinner(self, n: int, k: int) -> int:
#         return 1 if n == 1 else (k + self.findTheWinner(n - 1, k) - 1) % n + 1


# class Solution:
#     def findTheWinner(self, n: int, k: int) -> int:
#         winner = 1
#         for i in range(2, n + 1):
#             winner = (k + winner - 1) % i + 1
#         return winner
